package com.ljy.my_study.leetcode.最长回文子串;

/**
 * @author lijunying
 * @date 2021/1/8 8:01
 */
public class TestMain {

//    给你一个字符串 s，找到 s 中最长的回文子串。
//
//    示例 1：
//
//    输入：s = "babad"
//    输出："bab"
//    解释："aba" 同样是符合题意的答案。
//    示例 2：
//
//    输入：s = "cbbd"
//    输出："bb"
//    示例 3：
//
//    输入：s = "a"
//    输出："a"
//    示例 4：
//
//    输入：s = "ac"
//    输出："a"
//             
//
//    提示：
//
//            1 <= s.length <= 1000
//    s 仅由数字和英文字母（大写和/或小写）组成
//
//    来源：力扣（LeetCode）
//    链接：https://leetcode-cn.com/problems/longest-palindromic-substring

    public static void main(String[] args) {
        TestMain testMain=new TestMain();
        System.out.println(testMain.longestPalindrome("cbbd"));
    }

    public String longestPalindrome(String s) {
        if(s==null||s.length()==0){
            return s;
        }
        String subStr="";
        for(int i=0;i<s.length();i++){
            subStr=doLongestPalindrome(s,i,true,subStr);
            subStr=doLongestPalindrome(s,i,false,subStr);
        }
        return subStr;
    }


    private String doLongestPalindrome(String s,int index,boolean isOdd,String subStr) {
        int len=s.length();
        if(index>=len){
            return "";
        }
        int left=index;
        int right=index;
        if(!isOdd){
            right++;
        }
        int resultLeft=-1;
        int resultRight=-1;
        while(left>=0&&right<len){
            if(s.charAt(left)==s.charAt(right)){
                resultLeft=left;
                resultRight=right;
                left--;
                right++;
            }else{
                break;
            }
        }
        if(resultLeft!=-1){
            if(subStr.length()<resultRight-resultLeft+1){
                return s.substring(resultLeft,resultRight+1);
            }else{
                return subStr;
            }
        }
        return subStr;
    }
}
